This invention relates to a hardware implementation of the log Maximum A Posteriori (MAP) probability algorithm. More specifically, this invention relates to a programmable logic device that can be programmed to configure its logic elements to approximate the normalization of probability values used in the operation of logMAP decoders.
Programmable logic devices (xe2x80x9cPLDsxe2x80x9d) typically include (1) many regions of programmable logic, and (2) programmable interconnection resources for selectively conveying signals to, from, and/or between those logic region""s. Each logic region is programmable to perform any of several different, relatively simple logic functions. The interconnection resources are programmable to allow the logic regions to work together to perform much more complex logic functions than can be performed by any individual logic region. Examples of known PLDs are shown in U.S. Pat. Nos. 3,473,160, Re. 34,363, 5,689,195 and 5,909,126, and U.S. patent application Ser. No. 09/266,235, all of which are hereby incorporated by reference herein in their entireties.
One of the functions that can be implemented in a PLD is a log Maximum a Posteriori (logMAP) decoder, as used in turbo decoding. Turbo codes are a relatively recent coding and decoding technique that makes use of an iterative decoding scheme. Developed in,the early 1990s, turbo coding allows highly reliable data communication at signal-to-noise ratios very near the Shannon limit, which is defined as the minimum signal-to-noise ratio needed to communicate reliably over a given communication medium at a given spectral (bandwidth) efficiency. Turbo codes are described in a paper by C. Berrou entitled, xe2x80x9cNear Shannon Limit Error Correcting Coding and Decoding: Turbo Codes,xe2x80x9d Proceedings of ICC ""93, Geneva, Switzerland, pp. 1064-1070, May 1993, and the iterative decoding scheme is described in J. Hagenauer""s xe2x80x9cIterative (Turbo) Decoding of Systematic Concatenated Codes with MAP and SOVA Algorithms,xe2x80x9d Proceedings of the ITG Conference on Source and Channel Coding, Frankfurt Germany, pp. 1-9, October 1994.
The fundamental concept of a logMAP decoder is that it is a machine that determines the state (path) metrics and branch metrics of a given encoder. State metrics are defined as the probability that any state in the trellis is reached at any given time, while the branch metric is defined as the probability that any particular branch was traversed at any given time in the trellis. A trellis is a term which describes a tree in which a branch not only bifurcates into two or more branches but also in which two or more branches can merge into one. A trellis diagram is an infinite replication of the state diagram for an encoder. The nodes (states) at one level in the trellis are reached from the node states of the previous level by transitioning through one branch, as determined by the state diagram.
In the present invention, the state and branch metrics are represented by xcex1, xcex2, and xcex3. Alpha (xcex1) represents the forward state metric and is defined as the probability that any state will be reached during the forward path through the MAP decoder. Its counterpart, xcex2, is the backward state metric and is defined as the probability that any state will be reached in a backward recursion through the MAP decoder. Gamma (xcex3) is the branch metric and is defined as the probability that any given branch of the trellis will be traversed at any given time. For practical implementation, the calculation can be calculated in the logarithmic domain. This means that all multiplication becomes addition and division becomes subtraction. The normalization of xcex1 values, normally a division operation in the MAP decoder, thus becomes a subtraction operation in the logMAP decoder.
Fixed point hardware implementation requires that the xcex1 and xcex2 probabilities must be normalized to prevent overflow. One known method suggests that xcex1 values are normalized by deducting the largest xcex1 value from all xcex1 values generated in the trellis at any time. Typically, this is a multi-logic level operation, with the number of logic levels dependent on the constraint length of the logMAP decoder. In the first level of the comparison operation, pairs of xcex1 values are fed into a maximum value selection circuit where they are inputted into a comparator and a multiplexer (MUX). The MUX utilizes the output of the comparator to output the larger of the two xcex1s. These values are in turn paired and fed into another level of maximum value selection circuits which each outputs the larger of the two input values. This continues until the largest xcex1 has been isolated. The maximum xcex1 is then deducted from all the xcex1 values generated in the trellis. This means that the largest normalized value will be xe2x80x9c0xe2x80x9d. Because the xcex1 values represent the probabilities of any state in the trellis being reached, this normalization also ensures that the sum of the probabilities of all states in the trellis being reached must approximate unity, where unity (or 1.0) is the ideal sum of all states after normalization. A floor is normally used to prevent underflow.
The primary drawback of this method, however, is that Nsxe2x88x921 comparisons have to be made in order to isolate the largest xcex1, where Ns=2(Lxe2x88x921) and is defined as the number of states in the trellis of the logMAP decoder, and L, the constraint length, is defined as the number of memory elements used during the coding. Even when implemented as a tree, log2 (Ns) levels of comparison are required in determining the largest xcex1. In programmable logic, each level of compare requires two levels of logic: one for the comparator, and one for the 2:1 multiplexer which selects the larger value. Thus the determination of the largest xcex1 often comprises the largest logic requirement in the logMAP decoder, as well as the largest component of the propagation delay in the critical path of the decoder.
It would be desirable to provide a method of normalization utilizing programmable logic devices in which the logic requirements are greatly reduced without degrading the performance of the logMAP decoder.
It is an object of this invention to provide a programmable logic device that can be programmed to configure its logic elements to approximate the normalization of probability values used in the operation of logMAP decoders, thereby significantly reducing the number of logic levels required in the normalization operation. Such reduction is projected to increase decoder speeds of three times over known processes, without significantly degrading accuracy. Indeed, the increased decoder speeds may allow for an increased number of iterations within the turbo decoder utilizing the logMAP decoder that may result in greater accuracy than known systems. Thus, this invention takes advantage of the fact that the logMAP and MAP decoders are found to work even if the state metrics are not precisely normalized after every calculation. Instead, an approximate normalization is used which greatly reduces the level of logic resources.
In a preferred embodiment, the xcex1 probabilities are approximately normalized by calculating an approximate normalization value which is then deducted from all xcex1 values in the trellis at any time. Because the approximate normalization value can only be positive, all negative xcex1 values are necessarily excluded from the comparison by logically ANDing the most significant bit (MSB) of each xcex1 with the NOT of its own MSB. The resulting bits are then all bitwise ORed together, thus approximating a single normalization value. This approximate normalization value is then fed into a subtraction circuitry which subtracts the approximate normalization value from all xcex1 values and outputs the desired normalized xcex1 values.
In the case of programmable logic devices, one logic level is what will fit into a four-input look-up table, or a new level of logic starts after a carry. Examples of functions using carries are adders, subtractors, or comparators. In the case of ASICs, a logic level is defined as starting after a carry.
The arrangement just described produces, in two logical levels of logic, the approximate normalization value. This is true regardless of the number of states involved in the operation of the logMAP decoder. In traditional logMAP decoders, such calculation of normalization would require at least six logic levels for a MAP turbo decoder of constraint length L=4. Increasingly higher number of logic levels are required for greater values of Lxe2x80x94two additional logic levels for each additional L. Moreover, performing all of these functions in two logic levels reduces the use of the interconnection network, thereby speeding up this portion of the computation and allowing more iterations per time period.
In an alternative preferred embodiment, normalization is approximated by deducting a constant from the xcex1 values at every cycle, if any xcex1 exceeds 0. This is accomplished by ORing the MSBs of all the xcex1 values and inverting (negating) the result. The constant deducted from all the xcex1 values must be equal to or greater than twice the maximum value for xcex3, because in calculating state and branch metric values, it is known that 2|max xcex3|xe2x89xa7xcex1 (where xcex1 is the maximum positive xcex1). Ideally, the constant is set to a power of two, which simplifies the generation of the normalization value.
This alternative embodiment reduces the comparison operation to an Ns-input OR gate, where Ns is the number of states in the trellis. Therefore, the comparison operation will only require one level of logic, although if pre-fabricated circuitry such as programmable logic devices are used to implement the structure, more actual physical levels may be required (this is generally true as Ns becomes very large, e.g. Ns greater than 32). For example, in this embodiment, programmable logic devices with four-input look up tables (xe2x80x9cLUTxe2x80x9d) may be used to implement the logic. Using the LUT and CASCADE structures in known programmable logic devices (PLD) such as those available from the assignee hereof, up to thirty-two xcex1 values may be checked in parallel, with only two levels of logic, in a single comparison level.